package com.sicheng.蓝桥.省赛.十三届;

/**
 * * @author hxx
 * * @date 2022/4/28 11:35
 */
public class 数组切分_dp {
    /**
     * 【问题描述】
     * 已知一个长度为N NN的数组：A 1 A1A1, A 2 A2A2, A 3 A3A3, …A N ANAN 恰好是 1 ∼ N NN 的一个排列。
     * 现在要求你将 A AA 数组切分成若干个 (最少一个，最多 N NN 个) 连续的子数组
     * 并且每个子数组中包含的整数恰好可以组成一段连续的自然数。
     * 例如:
     * 对于 A AA= {1, 3, 2, 4}, 一共有 5 种切分方法：
     * {1}{3}{2}{4}：每个单独的数显然是 (长度为 1 的) 一段连续的自然数。
     * {1}{3, 2}{4}：{3, 2} 包含 2 到 3，是 一段连续的自然数，另外 {1} 和 {4} 显然也是。
     * {1}{3, 2, 4}：{3, 2, 4} 包含 2 到 4，是 一段连续的自然数，另外 {1} 显然也是。
     * {1, 3, 2}{4}：{1, 3, 2} 包含 1 到 3，是 一段连续的自然数，另外 {4} 显然也是。
     * {1, 3, 2, 4}：只有一个子数组，包含 1 到 4，是 一段连续的自然数。
     * 【输入格式】
     * 第一行包含一个整数 N NN。第二行包含 N NN 个整数，代表 A AA 数组。
     * 【输出格式】
     * 输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取
     * 模后的值
     * 【样例输入】
     * 4
     * 1 3 2 4
     * 【样例输出】
     * 5
     */
    static int mod = (int) 1e9 + 7;

    public static void main(String[] args) {
        int[] nums = {1, 3, 2, 4};
        //先初始化二维数组
        boolean[][] arr = new boolean[nums.length][nums.length];
        for (int i = 0; i < nums.length; i++) {
            int min = nums[i];
            int max = nums[i];
            for (int j = i; j < nums.length; j++) {
                min = Math.min(nums[j], min);
                max = Math.max(nums[j], max);
                if (max - min == j - i) {
                    arr[i][j] = true;
                }
            }
        }
//        System.out.println(arr);

        //dp部分
        int[] dp = new int[nums.length + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j][i - 1]) {
                    dp[i] = (dp[i] + dp[j]) % mod;
                }
            }
        }
        System.out.println(dp[nums.length]);
    }

}
